package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-09-11 21:02
 */

/**
 * 题目:
 * 给定一个二维矩阵 matrix，以下类型的多个请求：
 * 计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1)，右下角为 (row2,col2)。
 * 实现 NumMatrix 类：
 * NumMatrix(int[][] matrix)给定整数矩阵 matrix 进行初始化
 * int sumRegion(int row1, int col1, int row2, int col2)
 * 返回左上角(row1,col1)、右下角(row2,col2)的子矩阵的元素总和。
 */
public class Test25_二维子矩阵的和 {
    class NumMatrix {
        private int[][] presum;

        public NumMatrix(int[][] matrix) {
            presum = new int[matrix.length + 1][matrix[0].length + 1];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    presum[i + 1][j + 1] = presum[i][j + 1] + presum[i + 1][j] + matrix[i][j] - presum[i][j];
                }
            }
        }

        public int sumRegion(int row1, int col1, int row2, int col2) {
            return presum[row2 + 1][col2 + 1] - presum[row1][col2 + 1] - presum[row2 + 1][col1] + presum[row1][col1];
        }
    }
}
